// https://leetcode.cn/problems/linked-list-cycle-ii/
// Created by ade on 2022/7/27.
//

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_map < ListNode * , int > myMap;
        while (head) {
            if (myMap.find(head) == myMap.end()) {
                myMap[head] = 1;
                head = head->next;
            } else {
                return head;
            }
        }
        return nullptr;
    }
};